package gold.digger;

import gold.utils.InputUtil;
import gold.utils.OutPutUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC352 {
    public long startExecuteTime = System.currentTimeMillis();


    class SummaryRanges {

        TreeSet<int[]> set = new TreeSet<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[0];
            }
        });

        /**
         * Initialize your data structure here.
         */
        public SummaryRanges() {

        }

        public void addNum(int val) {
            int i = 0;
            int[] pre = null;
            Iterator<int[]> iterator = set.iterator();
            while (iterator.hasNext()) {
                int[] interval = iterator.next();
                if (val >= interval[0] && val <= interval[1]) return;//已经在区间中


                if (val == interval[0] - 1) {
                    interval[0] = val;
                    if (null != pre && pre[1] >= val - 1) {
                        pre[1] = interval[1];
                        iterator.remove();
                    }
                    break;
                }

                if (val == interval[1] + 1) {
                    interval[1] = val;
                    if (iterator.hasNext()) {
                        int[] next = iterator.next();
                        if (next[0] - 1 == val) {
                            interval[1] = next[1];
                            iterator.remove();
                        }
                    }
                    break;
                }

                ++i;
                pre = interval;
            }

            if (i == set.size()) set.add(new int[]{val, val});
        }

        public int[][] getIntervals() {
            int[][] res = new int[set.size()][2];
            int i = 0;
            for (int[] interval : set) {
                res[i++] = interval;
            }
            return res;
        }
    }

    /**
     * Your SummaryRanges object will be instantiated and called as such:
     * SummaryRanges obj = new SummaryRanges();
     * obj.addNum(val);
     * int[][] param_2 = obj.getIntervals();
     */

    public void run() {
        SummaryRanges solution = new SummaryRanges();
        int[] seq = InputUtil.toIntegerArray("[1,3,7,2,6]");
//        int[] seq = InputUtil.toIntegerArray("[1,9,2]");
        for (int i = 0; i < seq.length; i++) {
            solution.addNum(seq[i]);
            System.out.println("add " + seq[i] + " and array: " + OutPutUtil.doubleIntegerArrayToStr(solution.getIntervals()));
        }

    }

    public static void main(String[] args) throws Exception {
        LC352 an = new LC352();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
